package org.leetcode.hard.leetcode124;


import org.leetcode.TreeNode;

public class Solution {

    int maxSum =Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        DFS(root);
        return maxSum;
    }


    private int DFS(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = DFS(root.left);
        int right = DFS(root.right);

        left=Math.max(0,left);
        right=Math.max(0,right);

        maxSum = Math.max(maxSum, left + right + root.val);

        return Math.max(left, right) + root.val;

    }
}
